Noiseless/lossless data compression greatly increases communication speed and memory capacity without degrading data integrity. One conventional method of lossless data compression used for text compression is called autosophy data communication. In this process, each text word is replaced by a preassigned word-number or address token that is associated with the word. Only the address tokens are communicated from a source site to a destination site. Each of the sites contains identical libraries of words and the corresponding word-number or address token. When a destination site receives a string of address tokens, the destination site uses the library to reconstruct the string of words originally input at the source site. This scheme is simple to implement, but is text-based and has limited compression capability.
Many schemes exist to compress intelligence bearing signals, such as sound or voice. However, there is a significant need for faster schemes to compress intelligence bearing signals, particularly toll-grade speech, so that existing communication media, such as fiber optic telephone cables, can be used more efficiently. The present invention fulfills such a need.
An intelligence bearing signal is communicated from a source site to a destination site. The signal is in the form of a string of digitized analog signal samples. A sub-string dictionary, a linked list and an ID list are provided at the source site and the destination site. The sub-string dictionary has a plurality of entries. Each entry is a unique sub-string having a defined length. The linked list has a plurality of entries. The linked list entries include an address pointer to the start of each sub-string in the sub-string dictionary. The ID list has a plurality of entries. Each entry in the ID list contains the characteristics of each sub-string, and a pointer to the linked list entry that points to the first sub-string entry that has the characteristics of a respective sub-string. In the communication process, a string of digitized analog signal samples are parsed into a plurality of sub-strings. The sub-string dictionary and the ID list are then used to identify any sub-strings in the sub-string dictionary that correspond to any of the sub-strings obtained by the parsing operation. Only the address pointer in the linked list that correspond to any identified sub-strings are communicated from the source site to the destination site.